package P1线性结构.LeetCode单调栈;

import java.util.ArrayDeque;

public class LeetCode42 {
    public int trap(int[] height) {
        int ans = 0;
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int top = stack.pop();
                if (stack.isEmpty()) {
                    break;
                }
                int left = stack.peek();
                int w = i - left - 1;
                int h = Math.min(height[left], height[i]) - height[top];
                ans += w * h;
            }
            //栈为空 或者 当前比栈顶小或者等于 进栈
            stack.push(i);
        }
        return ans;
    }
}
